home *** CD-ROM | disk | FTP | other *** search
/ Amiga Games Extra 1996 September / Amiga Games Extra CD-ROM 9-1996.iso / userbox / publicdomain / vim-4.2 / macros / maze / maze_mac < prev    next >
Text File  |  1996-05-29  |  12KB  |  272 lines
  1. " These macros 'solve' any maze produced by the a-maze-ing maze.c program.
  2. " 
  3. " First, a bit of maze theory.
  4. " If you were put into a maze, a guaranteed method of finding your way
  5. " out of the maze is to put your left hand onto a wall and just keep walking,
  6. " never taking your hand off the wall. This technique is only guaranteed to
  7. " work if the maze does not have any 'islands', or if the 'exit' is on the
  8. " same island as your starting point. These conditions hold for the mazes
  9. " under consideration.
  10. " 
  11. " Assuming that the maze is made up of horizontal and vertical walls spaced
  12. " one step apart and that you can move either north, south, east or west,
  13. " then you can automate this procedure by carrying out the following steps.
  14. " 
  15. " 1. Put yourself somewhere in the maze near a wall.
  16. " 2. Check if you have a wall on your left. If so, go to step 4.
  17. " 3. There is no wall on your left, so turn on the spot to your left and step
  18. "    forward by one step and repeat step 2.
  19. " 4. Check what is directly in front of you. If it is a wall, turn on the
  20. "    spot to your right by 90 degrees and repeat step 4.
  21. " 5. There is no wall in front of you, so step forward one step and
  22. "    go to step 2.
  23. " 
  24. " In this way you will cover all the corridors of the maze (until you get back
  25. " to where you started from, if you do not stop).
  26. " 
  27. " By examining a maze produced by the maze.c program you will see that 
  28. " each square of the maze is one character high and two characters wide.
  29. " To go north or south, you move by a one character step, but to move east or
  30. " west you move by a two character step. Also note that in any position
  31. " there are four places where walls could be put - to the north, to the south,
  32. " to the east and to the west.
  33. " A wall exists to the north of you if the character to the north of
  34. " you is a _ (otherwise it is a space).
  35. " A wall exists to the east of you if the character to the east of you
  36. " is a | (otherwise it is a .).
  37. " A wall exists to the west of you if the character to the west of you
  38. " is a | (otherwise it is a .).
  39. " A wall exists to the south of you if the character where you are
  40. " is a _ (otherwise it is a space).
  41. " 
  42. " Note the difference for direction south, where we must examine the character
  43. " where the cursor is rather than an adjacent cell.
  44. " 
  45. " If you were implementing the above procedure is a normal computer language
  46. " you could use a loop with if statements and continue statements, 
  47. " However, these constructs are not available in vi macros so I have used
  48. " a state machine with 8 states. Each state signifies the direction you
  49. " are going in and whether or not you have checked if there is a wall on
  50. " your left.
  51. " 
  52. " The transition from state to state and the actions taken on each transition
  53. " are given in the state table below.
  54. " The names of the states are N1, N2, S1, S2, E1, E2, W1, W2, where each letter
  55. " stands for a direction of the compass, the number 1 indicates that the we
  56. " have not yet checked to see if there is a wall on our left and the number 2
  57. " indicates that we have checked and there is a wall on our left.
  58. " 
  59. " For each state we must consider the existence or not of a wall in a
  60. " particular direction. This direction is given in the following table.
  61. " 
  62. " NextChar table:
  63. " state        direction       vi commands
  64. "  N1              W               hF
  65. "  N2              N               kF
  66. "  S1              E               lF
  67. "  S2              S               F
  68. "  E1              N               kF
  69. "  E2              E               lF
  70. "  W1              S               F
  71. "  W2              W               hF
  72. " 
  73. " where F is a macro which yanks the character under the cursor into
  74. " the NextChar register (n).
  75. " 
  76. " State table:
  77. " In the 'vi commands' column is given the actions to carry out when in
  78. " this state and the NextChar is as given. The commands k, j, ll, hh move
  79. " the current position north, south, east and west respectively. The
  80. " command mm is used as a no-op command.
  81. " In the 'next state' column is given the new state of the machine after
  82. " the action is carried out.
  83. " 
  84. " current state        NextChar    vi commands  next state
  85. "      N1                 .            hh          W1
  86. "      N1                 |            mm          N2
  87. "      N2                 _            mm          E1
  88. "      N2               space          k           N1
  89. "      S1                 .            ll          E1
  90. "      S1                 |            mm          S2
  91. "      S2                 _            mm          W1
  92. "      S2               space          j           S1
  93. "      E1               space          k           N1
  94. "      E1                 _            mm          E2
  95. "      E2                 |            mm          S1
  96. "      E2                 .            ll          E1
  97. "      W1               space          j           S1
  98. "      W1                 _            mm          W2
  99. "      W2                 |            mm          N1
  100. "      W2                 .            hh          W1
  101. "
  102. " 
  103. " Complaint about vi macros:
  104. " It seems that you cannot have more than one 'undo-able' vi command
  105. " in the one macro, so you have to make lots of little macros and
  106. " put them together.
  107. "
  108. " I'll explain what I mean by an example. Edit a file and
  109. " type ':map Q rXY'. This should map the Q key to 'replace the
  110. " character under the cursor with X and yank the line'.
  111. " But when I type Q, vi tells me 'Can't yank inside global/macro' and
  112. " goes into ex mode. However if I type ':map Q rXT' and ':map T Y',
  113. " everything is OK. I`m doing all this on a Sparcstation.
  114. " If anyone reading this has an answer to this problem, the author would
  115. " love to find out. Mail to gregm@otc.otca.oz.au.
  116. "
  117. " The macros:
  118. " The macro to run the maze solver is 'g'. This simply calls two other
  119. " macros: I, to initialise everything, and L, to loop forever running
  120. " through the state table.
  121. " Both of these macros are long sequences of calls to other macros. All
  122. " of these other macros are quite simple and so to understand how this
  123. " works, all you need to do is examine macros I and L and learn what they
  124. " do (a simple sequence of vi actions) and how L loops (by calling U, which
  125. " simply calls L again).
  126. "
  127. " Macro I sets up the state table and NextChar table at the end of the file.
  128. " Macro L then searches these tables to find out what actions to perform and
  129. " what state changes to make.
  130. "
  131. " The entries in the state table all begin with a key consisting of the
  132. " letter 's', the current state and the NextChar.  After this is the
  133. " action to take in this state and after this is the next state to change to.
  134. "
  135. " The entries in the NextChar table begin with a key consisting of the
  136. " letter 'n' and the current state. After this is the action to take to
  137. " obtain NextChar - the character that must be examined to change state.
  138. "
  139. " One way to see what each part of the macros is doing is to type in the
  140. " body of the macros I and L manually (instead of typing 'g') and see
  141. " what happens at each step.
  142. "
  143. " Good luck.
  144. "
  145. " Registers used by the macros:
  146. " s (State)        - holds the state the machine is in
  147. " c (Char)         - holds the character under the current position
  148. " m (Macro)        - holds a vi command string to be executed later
  149. " n (NextChar)     - holds the character we must examine to change state
  150. " r (Second Macro) - holds a second vi command string to be executed later
  151. "
  152. set remap
  153. set nomagic
  154. set noterse
  155. set wrapscan
  156. "
  157. "================================================================
  158. " g - go runs the whole show
  159. "        I - initialise
  160. "        L - then loop forever
  161. map g   IL
  162. "
  163. "================================================================
  164. " I - initialise everything before running the loop
  165. "   G$?.^M - find the last . in the maze
  166. "        ^ - replace it with an X (the goal)
  167. "   GYKeDP - print the state table and next char table at the end of the file
  168. "       0S - initialise the state of the machine to E1
  169. "      2Gl - move to the top left cell of the maze
  170. map I   G$?.^GYKeDP0S2Gl
  171. "
  172. "================================================================
  173. " L - the loop which is executed forever
  174. "        Q - save the current character in the Char register
  175. "        A - replace the current character with an 'O'
  176. "       ma - mark the current position with mark 'a'
  177. "      GNB - on bottom line, create a command to search the NextChar table
  178. "            for the current state
  179. " 0M0E@m^M - yank the command into the Macro register and execute it
  180. "       wX - we have now found the entry in the table, now yank the
  181. "            following word into the Macro register
  182. "     `a@m - go back to the current position and execute the macro, this will
  183. "            yank the NextChar in register n
  184. "   GT$B$R - on bottom line, create a command to search the state table
  185. "            for the current state and NextChar
  186. " 0M0E@m^M - yank the command into the Macro register and execute it
  187. "      2WS - we have now found the entry in the table, now yank the
  188. "            next state into the State macro
  189. "       bX - and yank the action corresponding to this state table entry
  190. "            into the Macro register
  191. "      GVJ - on bottom line, create a command to restore the current character
  192. "       0H - and save the command into the second Macro register
  193. "     `a@r - go back to the current position and exectute the macro to restore
  194. "            the current character
  195. "       @m - execute the action associated with this state
  196. "        U - and repeat
  197. map L   QAmaGNB0M0E@mwX`a@mGT$B$R0M0E@m2WSbXGVJ0H`a@r@mU
  198. "
  199. "================================================================
  200. " U - no tail recursion allowed in vi macros so cheat and set U = L
  201. map U   L
  202. "
  203. "================================================================
  204. " S - yank the next two characters into the State register
  205. map S   "sy2l
  206. "
  207. "================================================================
  208. " Q - save the current character in the Char register
  209. map Q   "cyl
  210. "
  211. "================================================================
  212. " A - replace the current character with an 'O'
  213. map A   rO
  214. "
  215. "================================================================
  216. " N - replace this line with the string 'n'
  217. map N   C/n
  218. "
  219. "================================================================
  220. " B - put the current state
  221. map B   "sp
  222. "
  223. "================================================================
  224. " M - yank this line into the Macro register
  225. map M   "my$
  226. "
  227. "================================================================
  228. " E - delete to the end of the line
  229. map E   d$
  230. "
  231. "================================================================
  232. " X - yank this word into the Macro register
  233. map X   "myt 
  234. "
  235. "================================================================
  236. " T - replace this line with the string 's'
  237. map T   C/s
  238. "
  239. "================================================================
  240. " R - put NextChar
  241. map R   "np
  242. "
  243. "================================================================
  244. " V - add the letter 'r' (the replace vi command)
  245. map V   ar
  246. "
  247. "================================================================
  248. " J - restore the current character
  249. map J   "cp
  250. "
  251. "================================================================
  252. " H - yank this line into the second Macro register
  253. map H   "ry$
  254. "
  255. "================================================================
  256. " F - yank NextChar (this macro is called from the Macro register)
  257. map F   "nyl
  258. "
  259. "================================================================
  260. " ^ - replace the current character with an 'X'
  261. map ^   rX
  262. "
  263. "================================================================
  264. " YKeDP - create the state table, NextChar table and initial state
  265. " Note that you have to escape the bar character, since it is special to
  266. " the map command (it indicates a new line).
  267. map Y   osE1  k  N1       sE1_ mm E2       sE2| mm S1       sE2. ll E1
  268. map K   osW1  j  S1       sW1_ mm W2       sW2| mm N1       sW2. hh W1
  269. map e   osN1. hh W1       sN1| mm N2       sN2  k  N1       sN2_ mm E1
  270. map D   osS1. ll E1       sS1| mm S2       sS2  j  S1       sS2_ mm W1
  271. map P   onE1 kF nE2 lF nW1 G$JF nW2 hF nN1 hF nN2 kF nS1 lF nS2 G$JF E1
  272.